並び替えにFractional Indexingを使った場合、繰り返し並び替えるとどれぐらいの文字数・バイト数になるのか調べてみた

こんちは、 リテールアプリ共創部のmorimorikochanです。

最近Fractional Indexingを使う機会があったのですが、データベースに保存する際のサイズを考慮する必要があったので、試しにスクリプトを書いて検証してみました。
同じことを考える人もいるかもしれないと思ったので記事にしておきます。

Fractional Indexing とは？

Fractional Indexing とは、複数のデータ間に順序を持たせる際のアルゴリズムです。

例えば、"A"と"B"の2つのデータがこの順序で存在する場合、システム上で並び順としてAには"1"を、Bには"2"を設定したとします。
仮に別のデータ"C"がAとBの間に追加される場合、Fractional IndexingではCには"11"を指定します。
さらに仮に別のデータ"D"がCとBの間に追加される場合、Dには"12"を指定します。

これらのデータは並び順を文字列として捉えると以下のようにA→C→D→Bという順序になります

このように文字数をどんどん伸ばしていくことで、並び順の表現ができるアルゴリズムになっています。
このアルゴリズムはインターネットから出自を探すことはできませんでしたが、2017年段階でFigmaの公式サイトで紹介されています。
（Figmaで紹介されている方法では、0~1の範囲の小数点以下を利用しているため、上記の例とは少し異なります）

https://www.figma.com/blog/realtime-editing-of-ordered-sequences/

このアルゴリズムは、従来の並び順を表現する方法と比べると単一のデータの並び順を更新するだけで並び替えが実現できる点が優れています。
例えば先頭から連番を振るアルゴリズムの場合、"A"と"B"の間に"C"が追加されると、"C"に加えて"B"までもが並び順を変える必要があります。

何回並び替えるとどのぐらいの文字数・バイト数になる？

上記例では、2回並び替えると2桁になっていましたが、何回並び替えるとどのぐらいの文字数・バイト数になるのでしょうか？

普段よく使うRustおよびJavascriptそれぞれにFractional Indexingのライブラリが存在したため、それを利用して検証してみます。

前提条件

今回は最悪のケースでの文字数・バイト数が知りたかったため、以下の操作が行われた前提で検証しました。

3つの要素A,B,Cが並んでいる場合、以下の操作を6万回まで繰り返し、300回, 3000回, 30000回, 60000回時点でどのぐらいの文字数・バイト数になっているか検証します。

1. AとBの間にCを移動
2. AとCの間にBを移動
3. AとBの間にCを移動
4. …

JavaScriptで利用したライブラリはこちらです。

https://www.npmjs.com/package/fractional-indexing

また、コードは以下の通りです

import {generateKeyBetween} from "fractional-indexing"

const start = generateKeyBetween(null, null);
let end = generateKeyBetween(start, null)

for (let index = 0; index < 10*10000; index++) {
    end = generateKeyBetween(start, end)
    if (index===300) {
        console.log(`${index}: ${end}`)
    }
    if (index===3000) {
        console.log(`${index}: ${end}`)
    }
    if (index===30000) {
        console.log(`${index}: ${end}`)
    }
    if (index===60000) {
        console.log(`${index}: ${end}`)
    }
}

Rustで利用したライブラリはこちらです。

https://docs.rs/fractional_index/latest/fractional_index/

また、コードは以下の通りです

use fractional_index::FractionalIndex;

fn main() {
    let start = FractionalIndex::default();
    let mut end = FractionalIndex::new_after(&start);

    for i in 0..=10 * 10000 {
        end = FractionalIndex::new_between(&start, &end).unwrap();
        if i == 300 {
            println!("{}: {:?}", i, end.to_string());
        }
        if i == 3000 {
            println!("{}: {:?}", i, end.to_string());
        }
        if i == 30000 {
            println!("{}: {:?}", i, end.to_string());
        }
        if i == 60000 {
            println!("{}: {:?}", i, end.to_string());
        }
    }
}

結果

Javascriptのライブラリを使った場合の文字列の例

a000{長いので省略}000V

Rustのライブラリを使った場合の文字列の例

fff{長いので省略}fffd18

結果としては、一定の回数並び替えを行った場合でもライブラリによって大きく文字数・桁数が異なりました。
例えば6万回並び替えた場合、Javascriptの場合はおよそ10KBに達しているのに対し、Rustの場合は1KB未満となっており10%ほどのサイズになっています。

また、どちらも並び替え回数におおまかに比例して文字数・バイト数が増えています。　　
Javascriptの場合は1回の並び替えにつき約 0.1666 Byte、Rustの場合は1回の並び替えにつき約0.0157*XByteずつサイズが増えていることがわかります。

DynamoDBの1項目あたりの上限に達するためには何回並び替える？

例えばDynamoDBであれば、1つの項目の最大サイズは400KBと決まっています。
仮にJavascriptのライブラリを利用した場合、文字列が400KBに達するためには、400*1000/0.1666=240万回近く並び替えをしなければなりません。
この数字が許容できるかできないかはアプリケーションの要件次第ですが、多くのアプリケーションでは許容できるのではないかと思います。

ライブラリによって大きく変わる文字数・バイト数が変わる原因

結果が異なった原因については調査きれていませんが、それぞれのライブラリで利用している文字の範囲や実装方法が異なることが原因のようです。
Javascriptのライブラリの場合は62文字（0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz）を利用していますが、

https://github.com/rocicorp/fractional-indexing/blob/51050cdfeb8e30733b7351e2d3096995eac8b5c5/src/index.js#L5-L6

Rustのライブラリの場合は内部で文字列ではなくバイトで管理していました。

https://github.com/jamsocket/fractional_index/blob/4e796c767b3559574ffbf6436b485384032eb2b7/src/fract_index.rs#L12

おそらくですが、これらの違いが結果に影響しているはずだと考えています。

まとめ・その他所感

• 並び替えを行った際に必要な文字数・バイト数はライブラリによって大きく異なりました
• 今回の検証では、DynamoDBに格納できる範囲では240万回並び替えが可能なことがわかりました。
• 実行時間の面では、Rustのライブラリの方が早かったです
  • 体感としては1/5程度
• 実はFractionalIndexと似た仕組みをずっと頭で考えていて“おれが考えた最強の並び替え”だと思ってましたが、すでに概念が打ち立てられてることを知って人類の叡智すげーって思いました